﻿// SortAlgorithm.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include<queue>

using namespace std;


// 冒泡排序 时间O(N^2) 空间O(1) 稳定 与数据状况无关
// 内循环中当前值与下一个值比较，逆序就交换，直到把内循环范围内的最值推到顶端
void BubbleSort(vector<int>& arr) {
	if (arr.size() <= 1) return;
	for (int i = arr.size() - 1; i > 0; --i) {
		for (int j = 0; j < i; ++j) {
			if (arr[j] > arr[j + 1]) {
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

// 选择排序 时间O(N^2) 空间O(1) 稳定 与数据状况无关
// 在内循环中找到最小值位置minIdx、在外循环中与当前位置i的值交换
void SelectionSort(vector<int>& arr) {
	if (arr.size() <= 1) return;
	for (int i = 0; i < arr.size(); ++i) {
		int minIdx = i;
		for (int j = i + 1; j < arr.size(); ++j) {
			if (arr[minIdx] > arr[j]) minIdx = j;
		}
		int temp = arr[minIdx];
		arr[minIdx] = arr[i];
		arr[i] = temp;
	}
}

// 插入排序 时间O(N^2) 空间O(1) 稳定 与数据状况有关，与冒泡排序和选择排序相比常数项更优
// 外循环i从小到大，内循环每次在i-0范围内排序，新进入的值不断与前方位置的值交换，直到与前一位置的值满足正序要求时即可停止内循环
void InsertSort(vector<int>& arr) {
	if (arr.size() <= 1) return;
	for (int i = 1; i < arr.size(); ++i) {
		for (int j = i; j > 0 && arr[j] < arr[j - 1]; --j) {
			int temp = arr[j];
			arr[j] = arr[j - 1];
			arr[j - 1] = temp;
		}
	}
}

// 归并排序 时间O(NlogN) 空间O(1) 稳定 减少比较次数
// 左组排序、右组排序、利用辅助数组合并
// 小和问题和逆序对问题
void MergeSort(vector<int>& arr, const int L, const int R) {
	if (L >= R) return;
	int mid = L + ((R - L) >> 1);
	MergeSort(arr, L, mid);
	MergeSort(arr, mid + 1, R);

	// 利用辅助数组合并
	vector<int> newArr(arr.begin() + L, arr.begin() + R + 1);
	int i = L, j = mid + 1, k = L;
	while (i <= mid && j <= R) {
		arr[k++] = newArr[i-L] < newArr[j - L] ? newArr[i++] : newArr[j++];
	}
	while (i <= mid - L) {
		arr[k++] = newArr[i++];
	}
	while (j <= R - L) {
		arr[k++] = newArr[j++];
	}
	return;
}

// 小和问题，使用归并排序可以减少比较次数
int xiaohe(vector<int>& arr, const int L, const int R) {
	if (L >= R) return 0;
	int mid = L + (R - L) >> 1;
	int lastL = xiaohe(arr, L, mid);
	int lastR = xiaohe(arr, mid + 1, R);

	int curXiaoHe = 0;
	vector<int> newArr(arr.begin() + L, arr.begin() + R + 1);
	int i = 0, j = mid - L + 1, k = L;
	while (i <= mid - L && j <= R - L) {
		if (newArr[i] < newArr[j]) { // 注意是<，=时不计入小和
			curXiaoHe += newArr[i] * (R - L + 1 - j); // 比归并排序多加的逻辑
			arr[k++] = newArr[i++];
		}
		else
			arr[k++] = newArr[j++];
	}
	while (i <= mid - L) {
		arr[k++] = newArr[i++];
	}
	while (j <= R - L) {
		arr[k++] = newArr[j++];
	}
	return lastL + lastR + curXiaoHe;
}

// 堆排序 时间O(NlogN) 空间O(1) 不稳定
class HeapSort {
	// [3 4 0 2 7] -> [7 4 0 2 3]
	// 堆排序 O(N*logN)
	HeapSort(vector<int>& arr) {
		if (arr.size() <= 1) return;
		////先生成大根堆  heapInsert方式 O(N*logN)
		//for (int i = 0; i < arr.size(); ++i) { 
		//    heapInsert(arr, i);
		//}
		//先生成大根堆  heapify方式 O(N) 比heapInsert方式快
		for (int i = arr.size() - 1; i >= 0; --i) {
			heapify(arr, i, arr.size());
		}
		//再做popmax操作，将最大值放到最后（与堆的最后一个值交换），0位置向下调整堆
		// O(N*logN)
		int heapSize = arr.size() - 1;
		while (heapSize > 0) {
			swap(arr[0], arr[heapSize]);
			heapify(arr, 0, heapSize--);
		}
	}

private:
	// O(logN)
	// arr[0...idx-1]已经是大根堆，向上调整arr[idx]的位置
	void heapInsert(vector<int>& arr, int idx) {
		// 若当前节点大于父节点，则交换，直至达到合适位置
		while (arr[idx] > arr[(idx - 1) / 2])
		{
			swap(arr[idx], arr[(idx - 1) / 2]);
			idx = (idx - 1) >> 1;
		}
	}
	// O(logN)
	// arr[idx+1...heapSize]满足大根堆，向下调整arr[idx]的位置
	void heapify(vector<int>& arr, int idx, int heapSize) {
		int left = (idx << 1) + 1;
		// 若当前节点小于最大的子孩子则交换，直至到达合适位置
		while (left < heapSize)
		{
			int largChild = (left + 1 < heapSize && arr[left + 1] > arr[left]) ? left + 1 : left;

			if (arr[idx] >= arr[largChild]) break;
			swap(arr[idx], arr[largChild]);
			idx = largChild;
			left = (idx << 1) + 1;
		}
	}
};


// 快速排序 
class QuickSort {
public:
	QuickSort(vector<int>& arr) {
		quickSort_2_0(arr, 0, arr.size() - 1);
	}

private:
	// 荷兰国旗问题的简化版   额外空间复杂度O(N)
	// arr[L...R]范围上，根据arr[R]做划分值，
	// 将<=arr[R]的数据放前面，>arr[R]的数据放后面,
	// 最后arr[R]与最左边的>arr{R]（idx=lq)的数做交换
	// 递归调用，再在arr[L...lq-1],[lq+1...R]上调整
	void quickSort_1_0(vector<int>& arr, const int L, const int R) {
		if (L >= R) return;
		int midVal = arr[R];
		int lq = L - 1;
		for (int i = L; i < R; ++i) {
			if (arr[i] <= midVal) {
				swap(arr[i], arr[++lq]);
			}
		}
		swap(arr[R], arr[++lq]);
		quickSort_1_0(arr, L, lq - 1);
		quickSort_1_0(arr, lq + 1, R);
	}
	// 随机选择基值（令时间复杂度变为：O(N*log(N)),额外空间复杂度变为：O(log(N))）+荷兰国旗问题 ==> 快排本体  不稳定
	// arr[L...R]范围上，[L,R]中随机选择基值mid，根据mid做划分值，
	// 将<arr[R]的数据放前面,arr[R]的数据放中间，>arr[R]的数据放后面,
	// 递归调用，再在arr[L...less],[greater...R]上调整
	void quickSort_2_0(vector<int>& arr, const int L, const int R) {
		if (L >= R) return;
		int mid = arr[L + rand() % (R - L + 1)];    // [L,R]中随机选择基值
		int less = L - 1, greater = R + 1;
		for (int i = L; i < greater;) {
			if (arr[i] < mid) swap(arr[i++], arr[++less]);
			else if (arr[i] > mid) swap(arr[i], arr[--greater]);
			else ++i;
		}
		quickSort_2_0(arr, L, less);
		quickSort_2_0(arr, greater, R);
	}
};

// 希尔排序
class ShellSort {
public:
	ShellSort(vector<int>& arr) {
		vector<int> stepSeq(makeStepSeq(arr.size()));
		for (int step : stepSeq) {
			insertSort(arr, step);
		}
	}

private:
	// 插排
	void insertSort(vector<int>& arr, int step) {
		for (int i = 0; i < step; ++i) {
			for (int j = i + step; j < arr.size(); j += step) {
				int curIdx = j;
				while (curIdx - step >= 0 && arr[curIdx] < arr[curIdx - step]) {
					swap(arr[curIdx], arr[curIdx - step]);
					curIdx -= step;
				}
			}
		}
	}
	// 生成希尔序列
	vector<int> makeStepSeq(int len) {
		deque<int> res;
		for (int i = 1; i < len; i <<= 1) {
			res.push_front(i);
		}
		return vector<int>(res.begin(), res.end());
	}
};

// 27 39 29 36 7 126 38 39
// 桶排序O(N*log10_digit) 稳定 不基于比较的排序，需要样本数据满足桶的划分
void BucketSort(vector<int>& arr) {
	int maxVal = 0;
	for (int val : arr) {
		maxVal = max(maxVal, val);
	}
	int maxDigit = 0;  //最大的数有几个十进制位
	while (maxVal) {
		maxVal /= 10;
		++maxDigit;
	}

	for (int digit = 0; digit < maxDigit; ++digit)
	{
		vector<queue<int>> buckets(10);
		for (int val : arr) {  // val/(int)pow(10,digit) % 10提取第digit位的数字
			buckets[(val / (int)pow(10, digit)) % 10].push(val);
		}
		int i = 0;
		for (auto bkt : buckets) {
			while (!bkt.empty()) {
				arr[i++] = bkt.front();
				bkt.pop();
			}
		}
	}
}

// 计数排序 时间O(N) 空间O(n+maxVal-minVal) 稳定 不基于比较的排序，需要元素是整数
void CountingSort(vector<int>& arr) {
	// 找出最值
	int minVal = arr[0], maxVal = arr[0];
	for (int val : arr) {
		minVal = min(minVal, val);
		maxVal = max(maxVal, val);
	}
	// 统计出现次数
	vector<int> counts(maxVal - minVal + 1, 0);
	for (int val : arr) {
		++counts[val - minVal];
	}
	// 累加次数
	for (int i = 1; i < counts.size(); ++i) {
		counts[i] += counts[i - 1];
	}
	// 创建新数组，原数组从后往前遍历(保证稳定性)，将遇到的值放到合适位置
	vector<int> res(arr.size());
	for (int i = arr.size() - 1; i >= 0; --i) {
		res[--counts[arr[i] - minVal]] = arr[i];
	}
	arr = res;
}


int main()
{
	//cout << ((-1)>>1) << endl ;
	vector<int> arr;
	char c = ' ';
	while (c != '\n') {
		int temp;
		(cin >> temp).get(c);
		arr.push_back(temp);
	}
	//MergeSort(arr,0,arr.size()-1);
	//QuickSort sort(arr);
	//BucketSort(arr);
	//ShellSort sort(arr);
	CountingSort(arr);
	std::cout << "排序后：" << endl;
	for (int i = 0; i < arr.size(); ++i) {
		std::cout << arr[i] << ' ';
	}
	//string s1 = "23456";
	//string s2(s1.begin() + 1, s1.end());
	//cout << s2;
}
